package code.c02_list.cdLinkList;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/26 18:55
 * @package code.c02_list.cdLinkList
 * @description 双向循环链表实现类
 */

public class CDLinkListClass<E> {
    // 存放头结点
    DLinkNode<E> dhead;

    // 构造方法
    public CDLinkListClass() {
        dhead = new DLinkNode<>();
        dhead.prior = dhead;
        dhead.next = dhead;
    }

    /**
     * 返回序号为 i 的结点
     * @param i
     * @return
     */
    private DLinkNode<E> geti(int i){
        DLinkNode<E> p = dhead;
        int j =-1;
        while (j<i){
            j++;
            p = p.next;
        }
        return p;
    }

    // ===================== 基本运算 ============================

    /**
     * 整体创建链表：头插法
     *
     * @param a
     */
    public void createListF(E[] a){
        DLinkNode<E> s;

        for (int i = 0; i < a.length; i++) {
            // 新建一个结点
            s = new DLinkNode<>(a[i]);

            // 将结点 s 用头插法插入 双链表中
            s.next= dhead.next;
            dhead.next.prior =s;
            dhead.next =s;
            s.prior = dhead;
        }

    }

    /**
     * 整体创建链表：尾插法
     * @param a
     */
    public void createListR(E[] a){
        DLinkNode<E> s;
        // t 始终指向尾结点
        DLinkNode<E> t = dhead;

        for (int i = 0; i < a.length; i++) {
            // 新建结点 s
            s = new DLinkNode<E>(a[i]);
            // 尾插法插入数据
            t.next = s;
            s.prior = t;
            // t 重新指向 尾结点
            t= s;
        }

        // 连成双链表
        t.next = dhead;
        dhead.prior = t;
    }

    /**
     * 添加元素
     * @param e
     */
    public void add(E e){
        DLinkNode<E> s = new DLinkNode<>(e);
        DLinkNode<E> p = this.dhead;

        while (p.next!=dhead){
            p=p.next;
        }
        p.next =s;
        s.next=dhead;
        s.prior = p;
        dhead.prior =s;
    }

    /**
     * 求线性表的长度
     * @return
     */
    public int size(){
        DLinkNode<E> p = dhead;
        int cnt = 0;
        while (p.next!= dhead){
            cnt++;
            p =p.next;
        }
        return cnt;
    }

    /**
     * 设置线性表的长度
     * @param newLen
     */
    public void setSize(int newLen){
        int len = size();
        if (newLen < 0 || newLen > len){
            throw new IllegalArgumentException("设置长度：n不在有效的范围内。");
        }

        if (newLen == len){
            return;
        }

        DLinkNode<E> p = geti(newLen - 1);
        p.next = dhead;
        dhead.prior = p;
    }

    /**
     * 获取元素
     *
     * @param i
     * @return
     */
    public E getElem(int i){
        int len = size();
        if (i < 0 || i > len){
            throw new IllegalArgumentException("查找：n不在有效的范围内。");
        }

        DLinkNode<E> geti = geti(i);
        return geti.data;
    }

    /**
     * 设置序号 为 i 的元素为 e
     * @param i
     * @param e
     */
    public void setElem(int i,E e){
        int len = size();
        if (i < 0 || i > len){
            throw new IllegalArgumentException("设置：n不在有效的范围内。");
        }

        geti(i).data = e;
    }

    /**
     * 查找一个为 e的元素的序号
     * @param e
     * @return
     */
    public int getNo(E e){
        int j = 0;
        DLinkNode<E> p = dhead.next;
        while (p!=dhead && !p.data.equals(e)){
            j ++;
            p = p.next;
        }

        return p == dhead ? -1:j;
    }

    /**
     * 在第 i 个元素后面添加元素 e
     * @param i
     * @param e
     */
    public void insert(int i,E e){
        if (i <0 || i> size()){
            throw new IllegalArgumentException("插入：位置 i 不在有效的范围内。");
        }
        DLinkNode<E> s = new DLinkNode<>(e);
        DLinkNode<E> p =dhead=geti(i);
        s.next = p.next;
        p.next.prior =s;
        p.next =s;
        s.prior = p;
    }

    /**
     * 删除第 i 个元素
     * @param i
     */
    public void delete(int i){
        if (i <0 || i> size()){
            throw new IllegalArgumentException("插入：位置 i 不在有效的范围内。");
        }

        DLinkNode<E> p =dhead=geti(i);

        p.prior.next = p.next;
        p.next.prior = p.prior;
    }

    /**
     * 将线性表转为字符串
     * @return
     */
    public String toString(){
        StringBuilder ans = new StringBuilder();
        DLinkNode<E> p = dhead.next;
        while (p!=dhead){
            ans.append(p.data).append(" ");
            p = p.next;
        }

        return ans.toString();
    }
}

